package com.yun.algorithmproblem.leetcode;

public class Leetcode731 {
    public static void main(String[] args) {
        MyCalendarTwo obj = new MyCalendarTwo();
        obj.book(97, 100);
        obj.book(51, 65);
        obj.book(27, 46);
        obj.book(90, 100);
        obj.book(20, 32);
        obj.book(15, 28);
    }

    static class MyCalendarTwo {

        public MyCalendarTwo() {

        }

        public boolean book(int startTime, int endTime) {
            System.out.println(query(root, 0, N, startTime, endTime - 1));
            if (query(root, 0, N, startTime, endTime - 1) < 2) {
                update(root, 0, N, startTime, endTime - 1, 1);
                return true;
            }
            return false;
        }

        /**
         * 线段树模板
         */
        class Node {
            Node left, right;
            int val, add;
        }

        private final int N = (int) 1e9;
        private Node root = new Node();

        public void update(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val += val;
                node.add += val;
                return;
            }
            int mid = (start + end) >> 1;
            pushDown(node);
            if (l <= mid) {
                update(node.left, start, mid, l, r, val);
            }
            if (r > mid) {
                update(node.right, mid + 1, end, l, r, val);
            }
            pushUp(node);
        }

        public int query(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) {
                return node.val;
            }
            int mid = (start + end) >> 1, ans = 0;
            pushDown(node);
            if (l <= mid) {
                ans = query(node.left, start, mid, l, r);
            }
            if (r > mid) {
                ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
            }
            return ans;
        }

        private void pushUp(Node node) {
            node.val = Math.max(node.left.val, node.right.val);
        }

        private void pushDown(Node node) {
            if (node.left == null) {
                node.left = new Node();
            }
            if (node.right == null) {
                node.right = new Node();
            }
            if (node.add == 0) {
                return;
            }
            node.left.val += node.add;
            node.right.val += node.add;
            node.left.add += node.add;
            node.right.add += node.add;
            node.add = 0;
        }
    }
}
